package leetcode_tag.树;

import leetcode.TreeNode;

import java.util.Stack;

public class LeetCode98 {

    public static void main(String[] args) {
        System.out.println(Math.max(Integer.MAX_VALUE, 2147483647));
    }

    //递归
    public boolean isValidBST1(TreeNode root) {
        if (root == null)
            return true;
        return helper(root, null, null);
    }

    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) return true;

        int val = node.val;
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;

        if (!helper(node.right, val, upper)) return false;
        if (!helper(node.left, lower, val)) return false;
        return true;
    }

    private boolean helper1(TreeNode node, Integer min, Integer max) {
        if (node == null)
            return true;
        if (node.val > min && node.val < max) {
            return helper(node.left, min, node.val)
                    && helper(node.right, node.val, max);
        }
        return false;
    }

    //中序遍历 二叉搜索树是有序的
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        double lastNumber = - Double.MAX_VALUE;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.add(current);
                current = current.left;
            }
            current = stack.pop();
            if (current.val <= lastNumber)
                return false;
            lastNumber = current.val;
            current = current.right;
        }
        return true;
    }
}
